package com.nanbei.backyracking;

/**
 * @ClassDescription: 解数独(回溯算法)
 * @JdkVersion: 1.8
 * @Author: libs
 * @Created: 2024/7/16 11:33
 */
public class SudokuSolver {
    public static void main(String[] args) {
        char[][] chars = {{'5', '3', '.', '.', '7', '.', '.', '.', '.'}, {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};
        solveSudoku(chars);
        for (char[] aChar : chars) {
            System.out.println(new String(aChar));
        }

    }

    public static void solveSudoku(char[][] board) {
        // 用来记录行冲突 （某一行1-9数字的冲突）
        boolean[][] line = new boolean[9][9];
        // 用来记录列冲突 （某一列1-9数字的冲突）
        boolean[][] arrange = new boolean[9][9];
        // 记录3*3 小方格内的冲突  行/3*3+列/3
        boolean[][] table = new boolean[9][9];

        for (int i = 0; i < board.length; i++) {
            char[] chars = board[i];
            for (int j = 0; j < chars.length; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    line[i][num] = true;
                    arrange[j][num] = true;
                    table[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }
        dfs(0, 0, board, line, arrange, table);

    }

    private static boolean dfs(int i, int j, char[][] board, boolean[][] line, boolean[][] arrange, boolean[][] table) {

        // 查找下一个不是点的元素
        while (board[i][j] != '.') {
            if (j + 1 >= 9) {
                j = 0;
                i++;
            }else {
                j++;
            }
            if (i >= 9) {
                return true;
            }
        }


        for (int k = 1; k <= 9; k++) {
            if (line[i][k - 1] || arrange[j][k - 1] || table[i / 3 * 3 + j / 3][k - 1]) {
                continue;
            }
            // 标记冲突
            line[i][k - 1] = true;
            arrange[j][k - 1] = true;
            table[i / 3 * 3 + j / 3][k - 1] = true;
            board[i][j] = Integer.toString(k).charAt(0);

            // 当数据全部插入完成后无需回溯直接返回（回溯回将之前添加的元素全部覆盖掉）
            if (dfs(i, j , board, line, arrange, table)) {
                return true;
            }

            // 回溯
            board[i][j] = '.';
            line[i][k - 1] = false;
            arrange[j][k - 1] = false;
            table[i / 3 * 3 + j / 3][k - 1] = false;
        }

        return false;
    }


}
